1. Field of the Invention
The present invention relates to a communication packet receiving device, more particularly, to a receiving device in which communication packets received in the order different from transmission order are sorted into the transmission order.
2. Description of the Related Art
The packet communication network is a communication network in which finely divided data are accommodated in communication packets (referred to as packets, hereinafter), and communication packets are exchanged among transmitting/receiving devices. For example, the Internet is a representative packet communication network. A packet communication network is configured by connecting multiple transmission devices to each other. Examples of transmission devices include a network router (referred to as router, hereinafter) and a network switch (referred to as switch, hereinafter), which are used to transfer packets to the transmission destinations.
In a packet communication network, a communication packet may be discarded or destroyed in the transmission. This results from congestion of processes in a router or a switch which transfers the packet, sensitivity reduction in receiving a signal sent from a transmission line by which devices are connected, effects of external electromagnetic, or the like. In general, a packet loss caused by discard and destruction is detected by a protocol which operates in an application layer or a transport layer. Such a protocol control allows retransmitting a lost packet to ensure the integrity of data.
A retransmission of a packet results in that a packet which was transmitted earlier may arrive at the receiving device later than a packet which was transmitted later. That is, the order in transmitting packets may differ from the order in receiving them. Such a state is called packet disorder. However, it is expected in many applications to have no packet disorder. Therefore, if a packet disorder occurs, the receiving device sorts the packets in the transmission order, and transfers the data to an application in the correct order. For example, the transmitting device transmits packets with which sequence numbers indicating the packet transmission order are attached. The receiving device sorts the packets in the correct order by referring to the sequence numbers. At this time, the receiving device needs to have a memory (referred to as sorting buffer, hereinafter) for temporarily storing received packets for which a packet disorder occurs, in order to sort the packets properly.
It should be noted that a packet communication is not necessarily carried out in the one-to-one correspondence between transmitting/receiving devices. In general, a plurality of communication devices exchange packets one another. FIG. 1 is a conceptual diagram showing a situation in which a general receiving device receives packets from a plurality of transmitting devices. Referring to FIG. 1, there is shown a situation in which a receiving device 211 receives packets 10 from three transmitting devices 210-1 to 210-3 via a network 200. In FIG. 1, the packets 10 are shown with different shapes for the transmitting devices 210-1 to 210-3 for distinction. The numbers described in the packets 10 indicate sequence numbers 31 attached to the packets 10. The packets 10 transmitted by the plurality of the transmitting devices 210-1 to 210-3 are transferred to the receiving device 211 by a switch 201. The packets 10 may be lost resulting from discard and/or destruction in the transfer process.
The receiving device 211 includes sorting buffers 230-1 to 230-3; the number of the sorting buffers 230-1 to 230-3 corresponds to the number of the transmitting devices 210-1 to 210-3 with which the receiving device 211 is communicating. This is because the sequence numbers 31 of the packets 10 transmitted from the transmitting devices 210-1 to 210-3 have no correlation each other and the same sequence number 31 may be given to packets 10 transmitted from the different transmitting devices 210-1 to 210-3. The receiving device 211 needs to manage the sequence numbers 31 of packets 10 received from the respective transmitting devices 210-1 to 210-3, individually.
Shown here is an example in which the sequence numbers 31 are given in units of the transmitting devices 210-1 to 210-3, for simplicity; however, a plurality of application programs may be executed simultaneously on the transmitting devices 210-1 to 210-3. In addition, each application may further open a plurality of communication connections. In such cases, the receiving device 211 needs to manage the sequence numbers 31 for each connection.
In the following explanation, a flow is defined as a set of the packets 10 to which a series of the sequence numbers 31 are given. Flows are identified in units of transmitting/receiving devices, users, links, carrier wave frequencies, connections, sessions, and applications or the like, or in units of a combination thereof. It can be said that the required number of the sorting buffers 230-1 to 230-3 in the receiving device 211 is equal to the number of flows for which the receiving device 211 provides communications. The following techniques are disclosed for sorting the packets 10 by using the sorting buffers 230-1 to 230-3 prepared for each flow in this manner.
Japanese Patent Application Publication No. P2007-028653A (patent literature 1) discloses a data reception method to avoid an erroneous reproduction of data packets in a packet retransmission protocol in a receiver. The data reception method disclosed in patent literature 1 relates to an automatic retransmitting control which is called HARQ (hybrid automatic repeat-request) in a mobile communication. FIG. 2 shows the configuration of a MAC (media access control) sub-player of an RNC (radio network controller) which constitutes an UTRAN (UMTS terrestrial radio access network) in a mobile communication network disclosed in patent literature 1. The MAC sub-player 300 is called MAC-eu 301-1 to 301-n . Each of the MAC-eu301-1 to 301-n shown in FIG. 2 is associated with one user. In patent literature 1, the number of sorting buffer entities provided in the RNC is equal to the product of the number of users and the number of flows per one user. Therefore, the RNC in patent literature 1 includes sorting buffers which correspond to the total number of the flows.
In the technique of patent literature 1, the capacity of the sorting buffers is proportional to the total number of flows in the receiving device. Therefore, a receiving device which often deals with a large number of flows, such as a server, suffers from a problem that a large memory capacity is consumed for sorting buffers.
In general, a memory with a small capacity operates at a higher speed than that of a memory with a large capacity. When the required memory capacity is small, a high-speed memory, such as a cache memory in a microprocessor and an SRAM (static random access memory) can be used as sorting buffers. When the use of such a high-speed memory results in an insufficient capacity, on the other hand, it is inevitable to use a relatively low-speed memory, such a DRAM (dynamic random access memory), as a sorting buffer.
When the packets 10 are sorted for a large number of flows as in patent literature 1, the memory resource is consumed excessively for the sorting buffers. Accordingly, it is inevitable to use a low-speed memory with a large capacity. Therefore, the time required for memory access related to the packet sorting process is increased, causing a problem of reduction of the sorting process speed.
It should be noted that Japanese Patent Application Publication No. P2007-013510A (patent literature 2) discloses a packet communication system in which a high quality service can be provided inexpensively even when a communication packet is delayed or lost, or a communication failure occurs.